package com.study.algorithm.base.list;

import com.google.common.collect.Lists;
import com.study.algorithm.base.common.ListUtil;
import org.apache.commons.collections.CollectionUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * MergeSort
 *
 * @author wanghuilong
 * @version 1.0
 * @description merge sort
 * @date 2023/1/18 18:36
 */
public class MergeSort {


    public static void main(String[] args) {
        List<Integer> list = ListUtil.getRandomList(10);
        list = Lists.newArrayList(3,7,1,4,6,5,1);
        System.out.println(list);
        System.out.println(baseMergeSort(list));
//        Integer[] arr = new Integer[list.size()];
        int[] arr = ListUtil.getArr(list);
        process(arr,0,list.size()-1);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * the merge sort regular way
     */
    public static List<Integer> baseMergeSort(List<Integer> list) {
        if(CollectionUtils.isEmpty(list) || list.size() == 1) {
            return list;
        }
        int middleIndex = list.size() / 2;
        middleIndex = (middleIndex == 1?0:middleIndex);
        //make the left part been in order
        List<Integer> leftList = list.subList(0, middleIndex + 1);
        //make the right part been in order
        List<Integer> rightList = list.subList(middleIndex + 1, list.size());
        //take the left part and right part merge together as result
        return merge(baseMergeSort(leftList),baseMergeSort(rightList));
    }

    /**
     * put two list merge together with order
     * @param leftList
     * @param rightList
     * @return
     */
    private static List<Integer> merge(List<Integer> leftList, List<Integer> rightList) {
        List<Integer> resultList = new ArrayList<>(leftList.size() + rightList.size());
        int leftListIndex = 0;
        int rightListIndex = 0;
        while(rightListIndex < rightList.size() || leftListIndex < leftList.size()) {
            if(rightListIndex < rightList.size() && leftListIndex < leftList.size()) {
                if(leftList.get(leftListIndex) <= rightList.get(rightListIndex)) {
                    resultList.add(leftList.get(leftListIndex));
                    leftListIndex++;
                }else if(leftList.get(leftListIndex) >= rightList.get(rightListIndex)) {
                    resultList.add(rightList.get(rightListIndex));
                    rightListIndex++;
                }
            }

            if(rightListIndex >= rightList.size() && leftListIndex < leftList.size()) {
                resultList.add(leftList.get(leftListIndex));
                leftListIndex++;
            }
            if(leftListIndex >= leftList.size() && rightListIndex < rightList.size()) {
                resultList.add(rightList.get(rightListIndex));
                rightListIndex++;
            }
        }
        return resultList;
    }

    /**
     * the standard result for merge sort
     */
    public  static void process(int[] arr, int L , int R) {
        if(L == R) {
            return;
        }
        int mid = L + ((R - L) >> 1);
        process(arr,L,mid);
        process(arr,mid+1,R);
        merge(arr,L,mid,R);
    }

    private static void merge(int[] arr, int L, int M, int R) {
        int[] helper = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = M + 1;
        while(p1 <= M && p2 <= R) {
            helper[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= M) {
            helper[i++] = arr[p1++];
        }
        while (p2 <= R) {
            helper[i++] = arr[p2++];
        }
        for (int j = 0; j < helper.length; j++) {
            arr[L+j] = helper[j];
        }
    }


}
